'''
This file is part of Lampy.

Lampy is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Lampy is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Lampy.  If not, see <http://www.gnu.org/licenses/>.

Copyright 2011 Kevin Han
'''

"""Parse and unparse lambda calculus expressions."""
from utils import *
import integer

def findMatching(s, start, end, startI=0):
    """
    Return the indices of the first matching occurrences of start and end in s,
    starting at index startI, or None if not found.

    >>> findMatching('[[0[[00]]', '[[', ']]')
    (3, 9)

    >>> print findMatching('(((', '(', ')')
    None
    """
    while True:
        startI = s.find(start, startI)
        if startI == -1:
            return None
        endI = startI + len(start)
        while True:
            endI = s.find(end, endI)
            if endI == -1:
                break
            tested = s[startI + len(start):endI]
            if tested.count(start) == tested.count(end):
                return startI, endI + len(end)
            endI += len(end)
        startI += len(start)

def parse(s, nameToNode=None):
    """
    Transform a lambda-calculus expression into a parse tree for evaluation.
    
    The result is a node (one of the following):
    a. a name (1-char string)
    b. a function (a list with 2 values):
        1. parameter string ('/ab')
        2. body (a node)
    c. a list of nodes

    nameToNode is a mapping from names to nodes - surround names in square
    brackets. You can also do this with integers.

    >>> parse('x')
    'x'
    >>> parse('/x.x')
    ['/x', 'x']
    >>> parse('(/x.x)y')
    [['/x', 'x'], 'y']
    >>> parse('(/x.x/y.xy)((/x.x)z)/x.x')
    [['/x', ['x', ['/y', ['x', 'y']]]], [['/x', 'x'], 'z'], ['/x', 'x']]
    >>> parse('[I][I]', nameToNode=dict(I=['/x', 'x']))
    [['/x', 'x'], ['/x', 'x']]
    """
    # remove outer parentheses if needed
    if s.startswith('(') \
            and s.endswith(')') \
            and findMatching(s, '(', ')') == (0, len(s)):
        return parse(s[1:len(s) - 1])

    if isName(s):
        return s

    if s.startswith(FUNC_CHAR):
        params, body = s.split('.', 1)
        body = parse(body)
        return makeFunc(params[1:], body)

    result = []
    i = 0
    while i < len(s):
        char = s[i]
        if char == '(':
            start, end = findMatching(s, '(', ')', startI=i)
            inner = parse(s[start + 1: end - 1])
            if i == 0 and isCompound(inner):
                result += inner
            else:
                result.append(inner)
            i = end
        elif char == '[':
            start, end = findMatching(s, '[', ']', startI=i)
            name = s[start + 1: end - 1]
            if name.isdigit():
                result.append(integer.toNode(int(name)))
            else:
                try:
                    node = nameToNode[name]
                except KeyError:
                    raise KeyError('name %s not found in mapping' % name)
                result.append(node)
            i = end
        elif char == FUNC_CHAR:
            result.append(parse(s[i:]))
            break
        else:
            result.append(char)
            i += 1
    return result if len(result) > 1 else result[0]

def unparse(node, maxDepth=10, curDepth=0):
    """
    Return a string representation of a node.

    maxDepth controls how many levels it is willing to descend into a node
    before replacing it with "...". Levels are defined by sets of parentheses.

    >>> unparse('s')
    's'
    >>> unparse(['s'])
    's'
    >>> unparse(['/x', ['x']])
    '/x.x'
    >>> unparse([['/x', ['x']], 'y'])
    '(/x.x)y'
    >>> unparse([['/x', ['x', ['/y', ['x', 'y']]]], [['/x', 'x'], 'z'], ['/x', 'x']])
    '(/x.x/y.xy)((/x.x)z)/x.x'
    >>> unparse([['x', 'y'], 'z'])
    'xyz'
    >>> unparse(['z', ['x', 'y']])
    'z(xy)'
    >>> unparse(['z', ['x', 'y']], maxDepth=0)
    'z(...)'
    """
    if maxDepth is None:
        maxDepth = float('Inf')

    if curDepth > maxDepth:
        return '...'

    # make it easy to call recursively
    kwCur = dict(maxDepth=maxDepth, curDepth=curDepth)
    kwNext = dict(maxDepth=maxDepth, curDepth=curDepth + 1)

    if isName(node):
        return node
    if isFunc(node):
        params, body = splitFunc(node)
        return FUNC_CHAR + params + '.' + unparse(body, **kwCur)

    result = ''
    for i, innerNode in enumerate(node[:-1]):
        if not isName(innerNode) and not (isCompound(innerNode) and i == 0):
            result += '(%s)' % unparse(innerNode, **kwNext)
        else:
            result += unparse(innerNode, **kwCur)
    if isCompound(node[-1]):
        result += '(%s)' % unparse(node[-1], **kwNext)
    else:
        result += unparse(node[-1], **kwCur)
    return result

if __name__ == '__main__':
    import doctest

    doctest.testmod()
